﻿/******************************************************************************************************
Copyright (c) 2014 Steven Giacomelli (stevegiacomelli@gmail.com)

Permission is hereby granted, free of charge, to any person obtaining a copy of this
software and associated documentation files (the "Software"), to deal in the Software
without restriction, including without limitation the rights to use, copy, modify,
merge, publish, distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies
or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
******************************************************************************************************/

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;

namespace SharpGeo.Indexing
{
    /// <summary>
    /// A readonly R-Tree that spatially sorts Geometries
    /// </summary>
    public class ReadOnlyRTree<T> :
    SpatialIndex<T> where T : Geometry
    {
        #region Constructors

        /// <summary>
        /// Bulk loads an R-Tree with geometry
        /// </summary>
        /// <param name="data">The Geometries to bulk load into the R-Tree</param>
        public ReadOnlyRTree(List<T> data)
        {
            if (data == null || data.Contains(null))
                throw new ArgumentNullException("data",
                    Properties.Resources.ReadOnlyRTreeDataNullException);

            lock (this)
            {
                BulkLoad(data);
            }
        }

        #endregion Constructors

        #region Fields

        /// <summary>
        /// The maximum number of child nodes / data
        /// </summary>
        protected const int MaximumNodes = 32;

        /// <summary>
        /// The minimum number of child nodes / data
        /// </summary>
        protected const int MinimumNodes = 13;

        private Node _rootNode;

        #endregion Fields

        #region Properties

        /// <summary>
        /// The envelope of this RTree
        /// </summary>
        public override Envelope Envelope
        {
            get { return _rootNode.Envelope; }
        }

        #endregion Properties

        #region BulkLoading

        /// <summary>
        /// Bulk builds a node with the passed data at the indicated level
        /// </summary>
        /// <param name="data">The data to build the node with</param>
        /// <param name="level">The level being built</param>
        /// <returns>A bulk built node</returns>
        protected Node BulkBuildNode(List<T> data, int level)
        {
            if (data == null)
                throw new ArgumentNullException("data",
                    Properties.Resources.ReadOnlyRTreeDataNullException);

            if (data.Count <= MaximumNodes)
                return new Node(data);

            var indexNode = new Node();

            var subSliceSize = Math.Ceiling(((double)data.Count) / ((double)MaximumNodes));
            var sliceSize = subSliceSize * Math.Ceiling(Math.Sqrt(MaximumNodes));

            for (int i = 0; i < data.Count; i += (int)sliceSize)
            {
                var slice = data.GetRange(i, (i + (int)sliceSize) < data.Count ? (int)sliceSize : data.Count - i);

                if (level % 2 == 1)
                {
                    slice.Sort((a, b) =>
                    {
                        if (a.Envelope.MinX < b.Envelope.MinX)
                            return -1;
                        else if (a.Envelope.MinX > b.Envelope.MinX)
                            return 1;
                        return 0;
                    });
                }
                else
                {
                    slice.Sort((a, b) =>
                    {
                        if (a.Envelope.MinY < b.Envelope.MinY)
                            return -1;
                        else if (a.Envelope.MinY > b.Envelope.MinY)
                            return 1;
                        return 0;
                    });
                }

                for (int j = 0; j < slice.Count; j += (int)subSliceSize)
                {
                    indexNode.InsertNode(
                        BulkBuildNode(
                        slice.GetRange(j,
                        (j + (int)subSliceSize) < slice.Count ? (int)subSliceSize : slice.Count - j),
                        level + 1));
                }
            }

            return indexNode;
        }

        /// <summary>
        /// Bulk loads an R-Tree using the overlap minimizing top down algorithm
        /// </summary>
        /// <param name="data"></param>
        protected void BulkLoad(List<T> data)
        {
            if (data == null)
                return;

            //if the shapes to add is less than the maximum size than just build a leaf on the root and...
            if (data.Count <= MaximumNodes)
            {
                _rootNode = new Node(data);
                return;
            }

            _rootNode = new Node();

            //determine the target height of the tree
            var height = Math.Ceiling(Math.Log(data.Count, MaximumNodes));
            //determine the entries into the root
            var rootEntries = Math.Ceiling(data.Count / Math.Pow(MaximumNodes, height - 1));

            data.Sort((a, b) =>
            {
                if (a.Envelope.MinX < b.Envelope.MinX)
                    return -1;
                else if (a.Envelope.MinX > b.Envelope.MinX)
                    return 1;
                return 0;
            });

            var subSliceSize = Math.Ceiling(data.Count / rootEntries);
            var sliceSize = subSliceSize * Math.Ceiling(Math.Sqrt(rootEntries));

            for (int i = 0; i < data.Count; i += (int)sliceSize)
            {
                var slice = data.GetRange(i, (i + (int)sliceSize) < data.Count ? (int)sliceSize : data.Count - i);

                slice.Sort((a, b) =>
                {
                    if (a.Envelope.MinY < b.Envelope.MinY)
                        return -1;
                    else if (a.Envelope.MinY > b.Envelope.MinY)
                        return 1;
                    return 0;
                });

                for (int j = 0; j < slice.Count; j += (int)subSliceSize)
                {
                    _rootNode.InsertNode(BulkBuildNode(
                        slice.GetRange(j, (j + (int)subSliceSize) < slice.Count ? (int)subSliceSize : slice.Count - j), 1));
                }
            }

            Count = data.Count;
        }
        #endregion BulkLoading

        #region Query Methods

        /// <summary>
        /// Queries the RTree for all objects that intersect with the searchEnvelope
        /// </summary>
        /// <param name="searchEnvelope">The envelope to test for intersection with</param>
        /// <returns>A list of objects intersecting the searchEnvelope</returns>
        public override ReadOnlyCollection<T> QueryIntersection(Envelope searchEnvelope)
        {
            var matches = new List<T>();

            if (_rootNode.Envelope.Intersects(searchEnvelope))
            {
                matches.AddRange(QueryIntersection(_rootNode, searchEnvelope));
            }

            return new ReadOnlyCollection<T>(matches);
        }

        /// <summary>
        /// Queries a node in the RTree for intersection with the searchEnvelope
        /// </summary>
        /// <param name="searchNode">The node to query</param>
        /// <param name="searchEnvelope">The searchEnvelope to test for intersection with</param>
        /// <returns>A list of objects intersecting the searchNode and the searchEnvelope</returns>
        protected virtual List<T> QueryIntersection(Node searchNode, Envelope searchEnvelope)
        {
            var matches = new List<T>();

            if (searchNode == null)
                return matches;

            if (searchNode.IsLeaf)
            {
                if (searchNode.Envelope.Intersects(searchEnvelope))
                {
                    for (int i = 0; i < searchNode.Count; i++)
                    {
                        if (searchNode[i].Intersects(searchEnvelope))
                        {
                            matches.Add(searchNode.GetData(i));
                        }
                    }
                }

                return matches;
            }

            if (searchNode.IsIndex)
            {
                if (searchNode.Envelope.Intersects(searchEnvelope))
                {
                    for (int i = 0; i < searchNode.Count; i++)
                    {
                        var childNode = searchNode.GetChildNode(i);

                        if (childNode.Envelope.Intersects(searchEnvelope))
                        {
                            matches.AddRange(QueryIntersection(childNode, searchEnvelope));
                        }
                    }
                }
            }

            return matches;
        }

        #endregion Query Methods

        #region Node

        /// <summary>
        /// A class representing the nodes in an R-Tree
        /// </summary>
        sealed protected class Node
        {
            #region Constructors

            /// <summary>
            /// Creates a leaf node
            /// </summary>
            /// <param name="data">The data to fill the leaf node with</param>
            public Node(List<T> data)
            {
                _data = data;

                for (int i = 0; i < _data.Count; i++)
                {
                    _envelope += _data[i].Envelope;
                }
            }

            /// <summary>
            /// Creates an index node
            /// </summary>
            public Node()
            {
                _children = new List<Node>(MaximumNodes);
            }

            #endregion Constructors

            #region Fields

            private List<Node> _children = null;
            private List<T> _data = null;
            private Envelope _envelope = Envelope.Empty;
            #endregion Fields

            #region Properties

            /// <summary>
            /// Gets the number of children\data items stored in this node
            /// </summary>
            public int Count
            {
                get
                {
                    return _data == null ? _children.Count : _data.Count;
                }
            }

            /// <summary>
            /// Gets the node's envelope
            /// </summary>
            public Envelope Envelope
            {
                get
                {
                    return _envelope;
                }
            }

            /// <summary>
            /// True if this node is an index node
            /// </summary>
            public bool IsIndex { get { return _children != null; } }

            /// <summary>
            /// True if this node is a leaf node
            /// </summary>
            public bool IsLeaf { get { return _data != null; } }

            /// <summary>
            /// Gets the envelope at the specified index
            /// </summary>
            /// <param name="index">The index to get the envelope at</param>
            /// <returns>The envelope stored at the specified index</returns>
            public Envelope this[int index]
            {
                get
                {
                    return _data == null ? _children[index].Envelope : _data[index].Envelope;
                }
            }
            #endregion Properties

            #region Methods

            /// <summary>
            /// Gets the child node at the specified index
            /// </summary>
            /// <param name="index">The index to get the child node at</param>
            /// <returns>The child node</returns>
            public Node GetChildNode(int index)
            {
                if (_children != null)
                {
                    return _children[index];
                }
                return null;
            }

            /// <summary>
            /// Gets the data at the specified index
            /// </summary>
            /// <param name="index">The index to get the data at</param>
            /// <returns>The data</returns>
            public T GetData(int index)
            {
                if (_data != null)
                {
                    return _data[index];
                }
                return null;
            }

            /// <summary>
            /// Inserts a child node into the index
            /// </summary>
            /// <param name="node">The node to insert</param>
            public void InsertNode(Node node)
            {
#if DEBUG
                Debug.Assert(!(Count > MaximumNodes), "Attempt to insert more than the maximum nodes");
#endif
                //this should only be called on index nodes, silently ignore it
                if (_children == null)
                    return;

                //add the data
                _children.Add(node);

                //grow the envelope
                _envelope += node.Envelope;
            }
            #endregion Methods
        }

        #endregion Node
    }
}